/*
 * Copyright (c) 2022 Hong Jiahua
 * https://gitee.com/arrco/jh_set
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
/**
  * @file        jh_set.c
  * @brief       集合
  * @details     集合
  * @author      Hong Jiahua
  * @version     1.0.0
  * @date        2022-03-13
  * @copyright   2022 Hong Jiahua MIT License
  */
#include <stdio.h>
#include "jh_set.h"

/************************************************************************/
/*                                                                      */
/************************************************************************/
#include <stdlib.h>

#define JH_SET_MALLOC   malloc
#define JH_SET_FREE     free
/************************************************************************/
/*                                                                      */
/************************************************************************/
#include <string.h>

#define JH_SET_MEMCPY   memcpy
/************************************************************************/
/*                                                                      */
/************************************************************************/
#define NODE_HEIGHT(node)           ((node != NULL) ? ((node)->height) : -1)
#define NODE_HEAVY(node1, node2)    ((NODE_HEIGHT(node1) - NODE_HEIGHT(node2)) == 2)
#define NODE_MAX(x, y)              ((x) > (y) ? (x) : (y))
#define NODE_LEFT_CHILD             1
#define NODE_RIGHT_CHILD            2

typedef struct jh_set_node{
    int height;
    struct jh_set_node* parent;
    struct jh_set_node* left;
    struct jh_set_node* right;
    char value[];
} jh_set_node_t;

/************************************************************************/
/*                                                                      */
/************************************************************************/
/*查找最小节点*/
static jh_set_node_t* jh_set_min(jh_set_node_t* node) {
    if(node == NULL)
        return NULL;

    while(node->left != NULL)
        node = node->left;
    return node;
}

/*查找最大节点*/
static jh_set_node_t* jh_set_max(jh_set_node_t* node) {
    if(node == NULL)
        return NULL;

    while(node->right != NULL)
        node = node->right;
    return node;
}

/*LL rotation - LL旋转*/
static jh_set_node_t* jh_set_left_left_rotation(jh_set_node_t* node) {
    jh_set_node_t* nodeleft = node->left;
    jh_set_node_t* parent = node->parent;
    
    node->left = nodeleft->right;
    if(nodeleft->right)
        nodeleft->right->parent = node;
    nodeleft->right = node;
    node->parent = nodeleft;
    nodeleft->parent = parent;
    if(parent) {
        if(parent->left == node) {
            parent->left = nodeleft;
        } else {
            parent->right = nodeleft;
        }
    }

    node->height = NODE_MAX( NODE_HEIGHT(node->left), NODE_HEIGHT(node->right)) + 1;
    nodeleft->height = NODE_MAX( NODE_HEIGHT(nodeleft->left), node->height) + 1;

    return nodeleft;
}

/*RR rotation - RR旋转*/
static jh_set_node_t* jh_set_right_right_rotation(jh_set_node_t* node) {
    jh_set_node_t* noderight = node->right;
    jh_set_node_t* parent = node->parent;
    
    node->right = noderight->left;
    if(noderight->left)
        noderight->left->parent = node;
    noderight->left = node;
    node->parent = noderight;
    noderight->parent = parent;
    if(parent) {
        if(parent->left == node) {
            parent->left = noderight;
        } else {
            parent->right = noderight;
        }
    }

    node->height = NODE_MAX( NODE_HEIGHT(node->left), NODE_HEIGHT(node->right)) + 1;
    noderight->height = NODE_MAX( NODE_HEIGHT(noderight->right), node->height) + 1;

    return noderight;
}

/*LR rotation - LR旋转*/
static jh_set_node_t* jh_set_left_right_rotation(jh_set_node_t* node) {
    jh_set_right_right_rotation(node->left);
    return jh_set_left_left_rotation(node);
}

/*RL rotation - RL旋转*/
static jh_set_node_t* jh_set_right_left_rotation(jh_set_node_t* node) {
    jh_set_left_left_rotation(node->right);
    return jh_set_right_right_rotation(node);
}

/*搜索节点*/
static jh_set_node_t* jh_set_search(jh_set_t* set, jh_set_node_t* node, void* value) {
    if(node == NULL)
        return node;
    
    int ret = set->compare(value, node->value);
    
    while (ret != 0) {
        node = ret < 0 ? node->left : node->right;
        if(node == NULL)
            break;
        
        ret = set->compare(value, node->value);
    }

    return node;
}

/*创建节点*/
static jh_set_node_t* jh_set_create_node(jh_set_t* set, void* value) {
    jh_set_node_t* node;
    
    node = (jh_set_node_t *)JH_SET_MALLOC(sizeof(jh_set_node_t) + set->size);
    if(node == NULL)
        return NULL;
    
    JH_SET_MEMCPY(node->value, value, set->size);
    node->height = 0;
    node->parent = NULL;
    node->left = NULL;
    node->right = NULL;

    return node;
}

/*销毁节点*/
static void jh_set_destroy_node(jh_set_node_t* node) {
    JH_SET_FREE(node);
}

/*添加数据*/
static jh_set_node_t* jh_set_add(jh_set_t* set, jh_set_node_t* node, void* value) {
    jh_set_node_t* parenttree = NULL;
    int ret = 0;
    
    while(1) {
        if(node == NULL) {
            node = jh_set_create_node(set, value);
            if(node == NULL)
                return NULL;
            
            if(parenttree) {
                node->parent = parenttree;
                
                if(ret < 0) {
                    node->parent->left = node;
                } else if(ret > 0) {
                    node->parent->right = node;
                }
            }
            
            break;
        }
        
        ret = set->compare(value, node->value);
        parenttree = node;
        if(ret == 0)
            return NULL;
        
        node = ret < 0 ? node->left : node->right;
    }
    
    while(1) {
        if(node->parent == NULL)
            break;
        
        if(node->parent->left == node) {
            node = node->parent;
            if(NODE_HEAVY(node->left, node->right)) {
                node = set->compare(value, node->left->value) < 0 ? jh_set_left_left_rotation(node) : jh_set_left_right_rotation(node);
            }
        } else if(node->parent->right == node) {
            node = node->parent;
            if(NODE_HEAVY(node->right, node->left)) {
                node = set->compare(value, node->right->value) > 0 ? jh_set_right_right_rotation(node) : jh_set_right_left_rotation(node);
            }
        }
        node->height = NODE_MAX( NODE_HEIGHT(node->left), NODE_HEIGHT(node->right)) + 1;
    }
    
    return node;
}

/*删除数据*/
static jh_set_node_t* jh_set_delete(jh_set_t* set, jh_set_node_t* node, void* value) {
    void* targetvalue = value;
    int dir = 0, ret = 0;
    
    while(1) {
        if(node == NULL)
            return NULL;
        
        ret = set->compare(targetvalue, node->value);
        if(ret < 0) {
            node = node->left;
            dir = NODE_LEFT_CHILD;
        } else if(ret > 0) {
            node = node->right;
            dir = NODE_RIGHT_CHILD;
        } else {
            if((node->left) && (node->right)) {
                if(NODE_HEIGHT(node->left) > NODE_HEIGHT(node->right)) {
                    jh_set_node_t *max = jh_set_max(node->left);
                    JH_SET_MEMCPY(node->value, max->value, set->size);
                    targetvalue = node->value;
                    node = node->left;
                    dir = NODE_LEFT_CHILD;
                } else {
                    jh_set_node_t *min = jh_set_min(node->right);
                    JH_SET_MEMCPY(node->value, min->value, set->size);
                    targetvalue = node->value;
                    node = node->right;
                    dir = NODE_RIGHT_CHILD;
                }
                continue;
            } else {
                jh_set_node_t *delnode = node;
                node = node->left ? node->left : node->right;
                if(node) {
                    node->parent = delnode->parent;
                    if(dir == NODE_LEFT_CHILD) {
                        node->parent->left = node;
                    } else if(dir == NODE_RIGHT_CHILD) {
                        node->parent->right = node;
                    }
                } else {
                    if(dir == NODE_LEFT_CHILD) {
                        delnode->parent->left = NULL;
                        node = delnode->parent;
                        if(NODE_HEAVY(node->right, node->left)) {
                            node = NODE_HEIGHT(node->right->left) > NODE_HEIGHT(node->right->right) ? jh_set_right_left_rotation(node) : jh_set_right_right_rotation(node);
                        }
                        node->height = NODE_MAX(NODE_HEIGHT(node->left), NODE_HEIGHT(node->right)) + 1;
                    } else if(dir == NODE_RIGHT_CHILD) {
                        delnode->parent->right = NULL;
                        node = delnode->parent;
                        if(NODE_HEAVY(node->left, node->right)) {
                            node = NODE_HEIGHT(node->left->right) > NODE_HEIGHT(node->left->left) ? jh_set_left_right_rotation(node) : jh_set_left_left_rotation(node);
                        }
                        node->height = NODE_MAX(NODE_HEIGHT(node->left), NODE_HEIGHT(node->right)) + 1;
                    } else {
                        node = delnode->parent;
                    }
                }
                jh_set_destroy_node(delnode);
                break;
            }
        }
    }
    
    while(1) {
        if(node == NULL || node->parent == NULL) {
            break;
        }
        
        if(node->parent->left == node) {
            node = node->parent;
            if(NODE_HEAVY(node->right, node->left)) {
                node = NODE_HEIGHT(node->right->left) > NODE_HEIGHT(node->right->right) ? jh_set_right_left_rotation(node) : jh_set_right_right_rotation(node);
            }
        } else if(node->parent->right == node) {
            node = node->parent;
            if(NODE_HEAVY(node->left, node->right)) {
                node = NODE_HEIGHT(node->left->right) > NODE_HEIGHT(node->left->left) ? jh_set_left_right_rotation(node) : jh_set_left_left_rotation(node);
            }
        }
        node->height = NODE_MAX(NODE_HEIGHT(node->left), NODE_HEIGHT(node->right)) + 1;
    }

    return node;
}

/*销毁集合*/
static void jh_set_destroy(jh_set_node_t* node) {
    jh_set_node_t* delnode;
    
    while(node) {
        while(node->left) {
            node = node->left;
        }
        if(node->right) {
            node = node->right;
            continue;
        }

        delnode = node;
        node = node->parent;
        if(node) {
            if(node->left == delnode)
                node->left = NULL;
            else if(node->right == delnode)
                node->right = NULL;
        }
        jh_set_destroy_node(delnode);
    }

    return;
}

/************************************************************************/
/*                                                                      */
/************************************************************************/
/**
  * @brief      从集合的节点中获取数据
  * @param[in]  set         集合
  * @param[in]  usernode    数据结点
  * @param[out] value       数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
void jh_set_memcpy(jh_set_t* set, void* usernode, void* value) {
    JH_SET_MEMCPY(value, ((jh_set_node_t*)(usernode))->value, set->size);
}

/**
  * @brief      在集合中查找下一个数据
  * @param[in]  set         集合
  * @param[in]  usernode    数据结点
  * @param[out] value       数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_set_find_next_value(jh_set_t* set, void** usernode, void* value) {
    jh_set_node_t* node = *(jh_set_node_t**)usernode;
    if(node->right == NULL) {
        while(node->parent && (node->parent->left != node)) {
            node = node->parent;
        }
        node = node->parent;
        if(node) {
            JH_SET_MEMCPY(value, node->value, set->size);
            *(jh_set_node_t**)usernode = node;
            return 0;
        }
        return -1;
    }
    
    node = node->right;
    while(node->left != NULL) {
        node = node->left;
    }
    JH_SET_MEMCPY(value, node->value, set->size);
    *(jh_set_node_t**)usernode = node;
    return 0;
}

/**
  * @brief      在集合中查找上一个数据
  * @param[in]  set         集合
  * @param[in]  usernode    数据结点
  * @param[out] value       数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_set_find_prve_value(jh_set_t* set, void** usernode, void* value) {
    jh_set_node_t* node = *(jh_set_node_t**)usernode;
    if(node->left == NULL) {
        while(node->parent && (node->parent->right != node)) {
            node = node->parent;
        }
        node = node->parent;
        if(node) {
            JH_SET_MEMCPY(value, node->value, set->size);
            *(jh_set_node_t**)usernode = node;
            return 0;
        }
        return -1;
    }
    
    node = node->left;
    while(node->right != NULL) {
        node = node->right;
    }
    JH_SET_MEMCPY(value, node->value, set->size);
    *(jh_set_node_t**)usernode = node;
    return 0;
}

/**
  * @brief      在集合中查找第一个大于或等于value数值的数据节点
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
void* jh_set_lower_bound(jh_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return NULL;
    
    jh_set_node_t* node = set->root;
    if(node == NULL)
        return node;
    
    jh_set_node_t* retnode = NULL;
    int ret = set->compare(value, node->value);
    
    while (ret != 0) {
        node = ret < 0 ? retnode = node, node->left : node->right;
        if(node == NULL)
            break;
        
        ret = set->compare(value, node->value);
    }
    
    return ret == 0 ? (void*)node : (void*)retnode;
}

/**
  * @brief      在集合中查找第一个大于value数值的数据节点
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
void* jh_set_upper_bound(jh_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return NULL;
    
    jh_set_node_t* node = set->root;
    if(node == NULL)
        return node;
    
    jh_set_node_t* retnode = NULL;
    int ret = set->compare(value, node->value);
    
    while (1) {
        node = ret < 0 ? retnode = node, node->left : node->right;
        if(node == NULL)
            break;
        
        ret = set->compare(value, node->value);
    }
    
    return (void*)retnode;
}

/**
  * @brief      在集合中查找第一个数据节点
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
void* jh_set_begin(jh_set_t* set) {
    if(set == NULL)
        return NULL;
    
    return (void*)jh_set_min(set->root);
}

/**
  * @brief      在集合中查找最后一个数据节点
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
void* jh_set_end(jh_set_t* set) {
    if(set == NULL)
        return NULL;
    
    return (void*)jh_set_max(set->root);
}

/**
  * @brief      获取集合的数据数量
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval     >=0     集合的数据数量
  */
size_t jh_set_count(jh_set_t* set) {
    if(set == NULL)
        return 0;
    
    return set->count;
}

/**
  * @brief      判断集合是否为空
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval      1      集合为空
  * @retval      0      集合不为空
  * @retval     -1      失败
  */
int jh_set_is_empty(jh_set_t* set) {
    if(set == NULL)
        return -1;
    
    return set->root == NULL;
}

/**
  * @brief      在集合中查找数据
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
void* jh_set_find(jh_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return NULL;
    
    return (void*)jh_set_search(set, set->root, value);
}

/**
  * @brief      在集合中插入数据
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_set_insert(jh_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return -1;
    
    void *ret = jh_set_add(set, set->root, value);
    if(ret == NULL)
        return -1;
    set->root = ret;
    set->count++;
    return 0;
}

/**
  * @brief      删除集合中的数据
  * @param[in]  set     集合
  * @param[in]  value   数据项
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_set_erase(jh_set_t* set, void* value) {
    if(set == NULL || value == NULL)
        return -1;
    
    if(jh_set_search(set, set->root, value) == NULL)
        return -1;
    
    set->root = jh_set_delete(set, set->root, value);
    set->count--;
    return 0;
}

/**
  * @brief      清空集合
  * @param[in]  set     集合
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_set_clear(jh_set_t* set) {
    if(set == NULL)
        return -1;
    
    jh_set_destroy(set->root);
    set->root = NULL;
    set->count = 0;
    return 0;
}

/**
  * @brief      集合初始化
  * @param[in]  set     集合
  * @param[in]  size    每个数据项的大小
  * @param[in]  compare 指向用于比较两个数据项的函数指针
  *
  * @return     errcode
  * @retval      0      成功
  * @retval     -1      失败
  */
int jh_set_init(jh_set_t* set, size_t size, int (*compare)(const void*, const void*)) {
    if(set == NULL || compare == NULL)
        return -1;
    
    set->root = NULL;
    set->size = size;
    set->count = 0;
    set->compare = compare;
    
    return 0;
}

/**
  * @brief      集合创建
  * @param[in]  size    每个数据项的大小
  * @param[in]  compare 指向用于比较两个数据项的函数指针
  *
  * @return     jh_set_t* 集合
  * @retval     非NULL  成功
  * @retval     NULL    失败
  */
jh_set_t* jh_set_create(size_t size, int (*compare)(const void*, const void*)) {
    if(compare == NULL)
        return NULL;
    
    jh_set_t* set = (jh_set_t*)JH_SET_MALLOC(sizeof(jh_set_t));
    
    set->root = NULL;
    set->size = size;
    set->count = 0;
    set->compare = compare;
    
    return set;
}

/**
  * @brief      集合销毁
  * @param[in]  set     集合
  *
  * @return     无
  */
void jh_set_free(jh_set_t* set) {
    if(set == NULL)
        return;
    
    JH_SET_FREE(set);
}
